package com.example.demo.arithmetic.hash;

/**
 * 哈希表 实现一个简单的哈希表 便于理解
 */
public class HashTable {
    Entry[] table = new Entry[16];

    int size = 0;

    float loadFactor = 0.75f;

    int threshold = (int) (loadFactor * table.length);

    Object get(int hash, Object key) {
        // 求模运算替换为位运算 提高效率
        // 数组大小是2的n次方
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        } else {
            Entry entry = table[idx];
            while (entry != null) {
                if (entry.key.equals(key)) {
                    return entry.value;
                }
                entry = entry.next;
            }
        }
        return null;
    }

    void put(int hash, Object key, Object value) {
        int idx = hash & (table.length - 1);
        // 位置为空 直接放进去
        if (table[idx] == null) {
            table[idx] = new Entry(hash, key, value);

        } else {
            Entry p = table[idx];
            while (true) {
                // 是否有重复key
                if (p.key.equals(key)) {
                    p.value = value;
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value);

        }
        size++;

        if (size > threshold) {
            resize();
        }
    }

    private void resize() {
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            // 拿到链表头
            Entry p = table[i];
            if (p != null) {
                // 拆分链表 移动到新数组
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        a = p;
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        b = p;
                    }
                    p = p.next;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length);
    }

    Object remove(int hash, Object key) {
        int idx = hash & (table.length - 1);
        // 位置为空 直接放进去
        if (table[idx] == null) {
            return null;
        }

        Entry entry = table[idx];
        Entry prev = null;
        while (entry != null) {
            if (entry.key.equals(key)) {
                // 找到了,删除
                if (prev == null) {
                    table[idx] = entry.next;
                } else {
                    prev.next = entry.next;
                }
                size--;
                return entry.value;
            }
            prev = entry;
            entry = entry.next;
        }
        return null;
    }

    static class Entry {
        int hash;
        Object key;
        Object value;
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        HashTable table = new HashTable();
        table.put(1, "zhang", "张三");
        table.put(17, "li", "李四");
        table.put(2, "wang", "王五");
        System.out.println(table.size);


        table.put(1, "zhang", "张三2");
        table.put(3, "zhang2", "张三22");
        System.out.println(table.size);
        System.out.println(table.get(1, "zhang"));
    }
}
